/*
题目链接：https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/
	刘沛民	2024-12-3
*/

class Solution {
public:
    vector<vector<int>> dp;
    int getMoney(int left,int right)
    {
        if(left>=right)
        {
            return 0;
        }
        if(dp[left][right]!=-1)
        {
            return dp[left][right];
        }
        else
        {
            int ret=INT_MAX;
            int biggest=0;
            for(int i=left;i<=right;i++)
            {
                biggest=i;
                biggest+=max(getMoney(left,i-1),getMoney(i+1,right));
                ret=min(ret,biggest);
            }
            dp[left][right]=ret;
            return ret;
        }
    }
    int getMoneyAmount(int n) {
        dp.resize(n+1,vector<int>(n+1,-1));
        return getMoney(1,n);
    }
};
